package levelorder;

import entity.TreeNode;
import javafx.scene.control.TableRow;

import java.util.LinkedList;

public class MaxDepth {
    /*
    * 104. 二叉树的最大深度
    * 给定一个二叉树，找出其最大深度。
    * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
    * 说明: 叶子节点是指没有子节点的节点。
    * */
    public static void main(String[] args){

    }

    // 我的想法：层序遍历完后得知深度
    // 结果是很慢
    public int mySolution(TreeNode root){
        if(root == null)
            return 0;
        int depth = 0;
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()){
            int len = deque.size();
            while (len > 0){
                root = deque.pop();
                if(root.left != null) deque.add(root.left);
                if(root.right != null) deque.add(root.right);
                len--;
            }
            depth++;
        }
        return depth;
    }

    // 深度优先递归
    // 得知左子树深度l和右子树深度r后，该数最大深度为max(l, r) + 1
    // 效果很nice
    public int maxDepth(TreeNode root){
        if(root == null)
            return 0;
        else {
            int leftMax = maxDepth(root.left);
            int rightMax = maxDepth(root.right);
            return Math.max(leftMax, rightMax) + 1;
        }
    }
}
